// #define print(...)
using Iterator = vector<ListNode*>::iterator;
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.empty()) return NULL;
    return DivideAndConquer(lists.begin(),
                            lists.begin()+lists.size()-1);
}
// 分治
ListNode * DivideAndConquer(Iterator begin, Iterator end){
    if(begin == end) return *begin;
    auto mid = begin + (end-begin)/2;
    return mergeTwoLists(
            DivideAndConquer(begin, mid),
            DivideAndConquer(mid+1, end)
            );
}
};
